package Leetcode第二期;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author : K k
 * @date : 13:17 2020/10/1
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 *
 * 注意：
 *
 * 答案中不可以包含重复的四元组。
 *
 * 示例：
 *
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 *
 * 满足要求的四元组集合为：
 * [
 *   [-1,  0, 0, 1],
 *   [-2, -1, 1, 2],
 *   [-2,  0, 0, 2]
 * ]
 */
public class 四数之和_18 {
    List<List<Integer>> res=new ArrayList<>();
    Deque<Integer> path=new LinkedList<>();
    //会出现重复项
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        dfsSolver(nums,nums.length,0,target);
        return res;
    }

    private void dfsSolver(int[] nums, int len, int index, int target) {
        if (target==0 && path.size()==4){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i=index;i<len;i++){
            path.addLast(nums[i]);
            dfsSolver(nums,len,i+1,target-nums[i]);
            path.removeLast();
        }
    }

    public List<List<Integer>> fourSumA(int[] nums, int target) {
        List<List<Integer>> ans=new ArrayList<>();
        Arrays.sort(nums);//从小到大排序
        if (nums.length<=3||nums==null) return ans;
        int len=nums.length;

        for (int i=0;i<len;i++) {
           // if (nums[i] > 0) break; //当数字大于0时 不满足条件
            if (i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<len;j++){
                if (j>i+1&&nums[j]==nums[j-1]) continue;
                int left = j + 1;
                int right = len - 1;
                while (left<right){
                    int sum=nums[i]+nums[j]+nums[left]+nums[right];
                    if (sum==target){
                        ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while (left<right&&nums[left]==nums[left+1])left++;
                        while (left<right&&nums[right]==nums[right-1])right--;
                        left++;
                        right--;
                    }
                    else if(sum<target)left++;
                    else if (sum>target)right--;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        四数之和_18 x=new 四数之和_18();
        //System.out.println(x.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
        System.out.println(x.fourSum(new int[]{0,4,-5,2,-2,4,2,-1,4}, 12));
        
    }
}
